package LK_Algorithm;
 class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) {
         this.val = val;
     }
     ListNode(int val, ListNode next) {
         this.val = val;
         this.next = next;
     }
 }
public class Alg_Day_5 {
    /*给你单链表的头结点 head ，请你找出并返回链表的中间结点。
        如果有两个中间结点，则返回第二个中间结点。
        解题思路:快慢指针*/
    public ListNode middleNode(ListNode head) {
        //给定一个头结点为 head 的非空单链表，返回链表的中间结点。
        //如果有两个中间结点，则返回第二个中间结点。
        //解法：快慢指针
        if (head ==null){
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        while (fast !=null && fast.next != null){
            fast= fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
    /*给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
    * 解题思路:快慢指针,快指针先走n步,然后快慢指针在一同遍历.同时有一个指针记录前一个节点*/
    public ListNode removeNthFromEnd(ListNode head, int n) {
        /*记录头结点.防止删除第一个节点,同时也记录前一个节点*/
        ListNode res = new ListNode(-1);
        res.next = head;
        ListNode fast=head;
        ListNode slow=head;
        ListNode pre=res;
        /*快指针先走*/
        while (n>0){
            fast=fast.next;
            n--;
        }
        /*快慢指针遍历*/
        while (fast!=null){
            fast=fast.next;
            pre=slow;
            slow=slow.next;
        }
        /*删除*/
        pre.next=slow.next;
        return res.next;
    }
}
